package com.lsa.letcode.the96.uniqBsts;

import java.util.HashMap;
import java.util.Map;

public class Solution {
	private Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
	
	public int numTrees(int n) {
		int[] memo = new int[n+1];
		memo[0] = 1;
		memo[1] = 1;
		
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				memo[i] += memo[j - 1] *  memo[i - j];
			}
		}
		
		return memo[n];
	}
	
    public int numTreesRec(int n) {
    	if (n < 2){
        	return 1;
        }
        else {
        	Integer num = memo.get(n);
        	if (num != null) {
        		return num;
        	}
        	else {
        		int sum = 0;
        		for (int i = 1; i <= n; i++) {
        			int left = numTreesRec(i - 1);
        			int right = numTreesRec(n - i);
        			sum += left * right;
        		}
        		memo.put(n, sum);
        		return sum;
        	}
        }
    }
}